#include "Delaunay.hpp"
#include "../Graphics/AABB.hpp"
#include <Utility\TextProgressBar.hpp>

namespace zzz {

typedef DelaunayVertexSet::iterator vIterator;
typedef DelaunayVertexSet::const_iterator cvIterator;
typedef DelaunayTriangleSet::iterator tIterator;
typedef DelaunayTriangleSet::const_iterator ctIterator;
typedef DelaunayEdgeSet::iterator edgeIterator;
typedef DelaunayEdgeSet::const_iterator cedgeIterator;

void DelaunayTriangle::SetCircumCircle()
{
  Vector2f p0 = at(0)->first;
  Vector2f p1 = at(1)->first;
  Vector2f p2 = at(2)->first;

  float y10 = p1[1] - p0[1];
  float y21 = p2[1] - p1[1];

  bool b21zero = y21 > -EPSILON && y21 < EPSILON;

  if (y10 > -EPSILON && y10 < EPSILON) {
    if (b21zero)  { // All three vertices are on one horizontal line.
      if (p1[0] > p0[0]) {
        if (p2[0] > p1[0]) p1[0] = p2[0];
      } else {
        if (p2[0] < p0[0]) p0[0] = p2[0];
      }
      Center_[0] = (p0[0] + p1[0]) * 0.5f;
      Center_[1] = p0[1];
    } else { // Vertices_[0] and Vertices_[1] are on one horizontal line.
      float m1 = - (p2[0] - p1[0]) / y21;
      float mx1 = (p1[0] + p2[0]) * 0.5f;
      float my1 = (p1[1] + p2[1]) * 0.5f;
      Center_[0] = (p0[0] + p1[0]) * 0.5f;
      Center_[1] = m1 * (Center_[0] - mx1) + my1;
    }
  } else if (b21zero) { // Vertices_[1] and Vertices_[2] are on one horizontal line.
    float m0 = - (p1[0] - p0[0]) / y10;
    float mx0 = (p0[0] + p1[0]) * .5F;
    float my0 = (p0[1] + p1[1]) * .5F;
    Center_[0] = (p1[0] + p2[0]) * .5F;
    Center_[1] = m0 * (Center_[0] - mx0) + my0;
  } else { // 'Common' cases, no multiple vertices are on one horizontal line.
    float m0 = - (p1[0] - p0[0]) / y10;
    float m1 = - (p2[0] - p1[0]) / y21;
    float mx0 = (p0[0] + p1[0]) * .5F;
    float my0 = (p0[1] + p1[1]) * .5F;
    float mx1 = (p1[0] + p2[0]) * .5F;
    float my1 = (p1[1] + p2[1]) * .5F;
    Center_[0] = (m0 * mx0 - m1 * mx1 + my1 - my0) / (m0 - m1);
    Center_[1] = m0 * (Center_[0] - mx0) + my0;
  }

  Vector2f dp = p0 - Center_;
  R2_ = dp.LenSqr();  // the radius of the circumcircle, squared
  R_ = Sqrt(R2_);  // the proper radius

  // Version 1.1: make R2_ slightly higher to ensure that all edges
  // of co-circular vertices will be caught.
  // Note that this is a compromise. In fact, the algorithm isn't really
  // suited for very many co-circular vertices.
  R2_ *= 1.000001f;
}

// Function object to check whether a DelaunayTriangle has one of the vertices in SuperTriangle.
// operator() returns true if it does.
class VertexInSuperTriangle
{
public:
  VertexInSuperTriangle(const DelaunayVertex SuperTriangle[3]) : pSuperTriangle_(SuperTriangle)  {}
  bool operator()(const DelaunayTriangle& tri) const {
    for (int i = 0; i < 3; i++) {
      const DelaunayVertex * p = tri[i];
      if (p == pSuperTriangle_ || p == pSuperTriangle_+1 || p == pSuperTriangle_+2) 
        return true;
    }
    return false;
  }
protected:
  const DelaunayVertex *pSuperTriangle_;
};

// Function object to check whether a DelaunayTriangle is 'completed', i.e. doesn't need to be checked
// again in the algorithm, i.e. it won't be changed anymore.
// Therefore it can be removed from the workset.
// A DelaunayTriangle is completed if the circumcircle is completely to the left of the current Vector2f.
// If a DelaunayTriangle is completed, it will be inserted in the output set, unless one or more of it's vertices
// belong to the 'super DelaunayTriangle'.
class CompleteTriangle {
public:
  CompleteTriangle(cvIterator itVertex, DelaunayTriangleSet& output, const DelaunayVertex SuperTriangle[3])
  : itVertex_(itVertex), Output_(output), pSuperTriangle_(SuperTriangle) {
  }

  bool operator()(const DelaunayTriangle& tri) const {
    bool b = tri.IsLeftOf(itVertex_);
    if (b) {
      VertexInSuperTriangle thv(pSuperTriangle_);
      if (! thv(tri)) Output_.push_back(tri);
    }
    return b;
  }

protected:
  DelaunayVertexSet::const_iterator itVertex_;
  DelaunayTriangleSet& Output_;
  const DelaunayVertex* pSuperTriangle_;
};

// Function object to check whether Vector2f is in circumcircle of DelaunayTriangle.
// operator() returns true if it does.
// The edges of a 'hot' DelaunayTriangle are stored in the edgeSet edges.
class VertexInCircumCircle {
public:
  VertexInCircumCircle(cvIterator itVertex, DelaunayEdgeSet& edges) 
  : itVertex_(itVertex), Edges_(edges) {
  }

  bool operator()(const DelaunayTriangle& tri) const {
    bool b = tri.CCEncompasses(itVertex_);
    if (b) {
      HandleEdge(tri[0], tri[1]);
      HandleEdge(tri[1], tri[2]);
      HandleEdge(tri[2], tri[0]);
    }
    return b;
  }

protected:
  void HandleEdge(const DelaunayVertex * p0, const DelaunayVertex * p1) const {
    const DelaunayVertex *pVertex0;
    const DelaunayVertex *pVertex1;

    // Create a normalized DelaunayEdge, in which the smallest Vector2f comes first.
    if (p0->first < p1->first) {
      pVertex0 = p0;
      pVertex1 = p1;
    } else {
      pVertex0 = p1;
      pVertex1 = p0;
    }

    DelaunayEdge e(pVertex0, pVertex1);

    // Check if this DelaunayEdge is already in the buffer
    edgeIterator found = Edges_.find(e);

    if (found == Edges_.end()) Edges_.insert(e);    // no, it isn't, so insert
    else Edges_.erase(found);              // yes, it is, so erase it to eliminate double edges
  }

  cvIterator itVertex_;
  DelaunayEdgeSet& Edges_;
};

void Delaunay::Triangulate(const vector<Vector2f>& vertices, vector<Vector3i>& output)
{
  DelaunayVertexSet vset;
  vset.reserve(vertices.size());
  for (zuint i=0; i<vertices.size(); i++) {
    vset.push_back(make_pair(vertices[i],i));
  }
  sort(vset.begin(), vset.end());
  DelaunayTriangleSet tset;
  DoTriangulate(vset, tset);

  output.clear();
  output.reserve(tset.size());
  for (DelaunayTriangleSet::iterator ti=tset.begin();ti!=tset.end();ti++) {
    output.push_back(Vector3i(ti->at(0)->second, ti->at(1)->second, ti->at(2)->second));
  }
}

void Delaunay::DoTriangulate(const DelaunayVertexSet& vertices, DelaunayTriangleSet& output)
{
  if (vertices.size() < 3) return;  // nothing to handle

  AABB<2, float> aabb;
  for (DelaunayVertexSet::const_iterator di=vertices.begin(); di!=vertices.end(); di++)
    aabb+=di->first;

  float xMin = aabb.Min()[0];
  float yMin = aabb.Min()[1];
  float xMax = aabb.Max()[0];
  float yMax = aabb.Max()[1];

  float dx = xMax - xMin;
  float dy = yMax - yMin;

  // Make the bounding box slightly bigger, just to feel safe.
  float ddx = dx * 0.01F;
  float ddy = dy * 0.01F;

  xMin -= ddx;
  xMax += ddx;
  dx += 2 * ddx;

  yMin -= ddy;
  yMax += ddy;
  dy += 2 * ddy;

  // Create a 'super DelaunayTriangle', encompassing all the vertices. We choose an equilateral DelaunayTriangle with horizontal base.
  // We could have made the 'super DelaunayTriangle' simply very big. However, the algorithm is quite sensitive to
  // rounding errors, so it's better to make the 'super DelaunayTriangle' just big enough, like we do here.
  DelaunayVertex vSuper[3];

  vSuper[0].first = Vector2f(xMin - dy * C_SQRT3 / 3.0F, yMin);  // Simple highschool geometry, believe me.
  vSuper[1].first = Vector2f(xMax + dy * C_SQRT3 / 3.0F, yMin);
  vSuper[2].first = Vector2f((xMin + xMax) * 0.5F, yMax + dx * C_SQRT3 * 0.5F);

  DelaunayTriangleSet workset;
  workset.reserve(vertices.size());
  workset.push_back(DelaunayTriangle(vSuper, vSuper+1, vSuper+2));

  TextProgressBar bar("Delaunay Triangulating");
  bar.SetMaximum(vertices.size()-1);
  bar.SetMinimum(0);
  bar.Start();
  for (DelaunayVertexSet::const_iterator itVertex = vertices.begin(); itVertex != vertices.end(); itVertex++)
  {
    bar.DeltaUpdate();
    // First, remove all 'completed' triangles from the workset.
    // A DelaunayTriangle is 'completed' if its circumcircle is entirely to the left of the current Vector2f.
    // Vertices are sorted in x-direction (the set container does this automagically).
    // Unless they are part of the 'super DelaunayTriangle', copy the 'completed' triangles to the output.
    // The algorithm also works without this step, but it is an important optimalization for bigger numbers of vertices.
    // It makes the algorithm about five times faster for 2000 vertices, and for 10000 vertices,
    // it's thirty times faster. For smaller numbers, the difference is negligible.
    tIterator itEnd = remove_if(workset.begin(), workset.end(), CompleteTriangle(itVertex, output, vSuper));

    DelaunayEdgeSet edges;

    // A DelaunayTriangle is 'hot' if the current Vector2f v is inside the circumcircle.
    // Remove all hot triangles, but keep their edges.
    itEnd = remove_if(workset.begin(), itEnd, VertexInCircumCircle(itVertex, edges));
    workset.erase(itEnd, workset.end());  // remove_if doesn't actually remove; we have to do this explicitly.

    // Create new triangles from the edges and the current Vector2f.
    for (edgeIterator it = edges.begin(); it != edges.end(); it++)
      workset.push_back(DelaunayTriangle((*it)[0], (*it)[1], & (* itVertex)));

//    sort(workset.begin(), workset.end());
  }
  bar.End();
  // Finally, remove all the triangles belonging to the 'super DelaunayTriangle' and move the remaining
  // triangles tot the output; remove_copy_if lets us do that in one go.
  tIterator where = output.begin();
  remove_copy_if(workset.begin(), workset.end(), inserter(output, where), VertexInSuperTriangle(vSuper));
}

void Delaunay::TrianglesToEdges(const DelaunayTriangleSet& triangles, DelaunayEdgeSet& edges)
{
  for (ctIterator it = triangles.begin(); it != triangles.end(); ++it)
  {
    HandleEdge((*it)[0], (*it)[1], edges);
    HandleEdge((*it)[1], (*it)[2], edges);
    HandleEdge((*it)[2], (*it)[0], edges);
  }
}

void Delaunay::HandleEdge(const DelaunayVertex * p0, const DelaunayVertex * p1, DelaunayEdgeSet& edges)
{
  const DelaunayVertex * pV0(NULL);
  const DelaunayVertex * pV1(NULL);

  if (p0->first < p1->first) {
    pV0 = p0;
    pV1 = p1;
  } else {
    pV0 = p1;
    pV1 = p0;
  }

  // Insert a normalized DelaunayEdge. If it's already in edges, insertion will fail,
  // thus leaving only unique edges.
  edges.insert(DelaunayEdge(pV0, pV1));
}
};  // namespace zzz